package main
import "fmt"
/*
	给定一个n个元素有序的(升序)整形数组nums和一个目标值target，写一个函数搜索nums种的target，如果目标存在返回下标，否则返回-1
	1.假设nums中所有元素不重复
	2.n将在[1,10000]之间
	3.nums中每个元素都将在[-9999, 9999]之间
*/
func search(nums []int, target int) int {
	//升序元素查找，可以使用二分查找
	//首先判断特殊情况，数组为空
	if len(nums)<=0{
		return -1
	}
	//开始使用二分查找
	start := 0
	end := len(nums)-1
	for{
		// 我的解法：middle := (start+end)/2
		middle := (start+end)>>1   //变成位运算会快好多！！
		if(start >= end){
			break
		}
		if nums[middle]==target{
			return middle
		}else if nums[middle]>target{
			//target在middle左侧
			end = middle-1
		}else{
			//target在middle右侧
			start = middle+1
		}
	}
	if nums[start]==target{
		return start
	}else{
		return -1
	}
}

func main(){
	nums := []int{-1,0,3,5,9,12}
	target := 9
	index :=search(nums, target)
	fmt.Println("find",target,"in nums index is ",index)
	target = 2
	index = search(nums, target)
	fmt.Println("find",target,"in nums index is ",index)
}
